package com.waiting.thread;

/**
 * @Description
 * @Author bjweitingting
 * @Date 2019/3/8
 **/
public class UniqueBinarySearchTrees96 {
    public static void main(String[] args) {

    }

    public int numTrees(int n) {
        if (n == 1) {
            return 1;
        }
        int[] tmp = new int[n + 1];
        tmp[0] = 1;
        tmp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                tmp[i] += tmp[j] * tmp[i - 1 - j];
            }
        }
        return tmp[n];
    }
}
